原题地址：删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
解答
遍历找到有重复的节点，然后先删除重复的节点，再删除被重复的节点。具体的实现代码如下：
/**
* @param {ListNode} head
* @return {ListNode}
*/
const deleteDuplicates1 = function(head) {
// 额外的头节点
let preHead = new ListNode(null);
preHead.next = head;
// 遍历用节点
let node = preHead;
while (node && node.next && node.next.next) {
// 发现有重复节点
if (node.next.val === node.next.next.val) {
// 先删除所有的重复节点
while (node.next.next && node.next.val === node.next.next.val) {
node.next.next = node.next.next.next;
}
// 再删除被重复的节点
node.next = node.next.next;
} else {
// 没有重复，直接后移
node = node.next;
}
}
return preHead.next;
};
测试：
let start = new Date();
const test = deleteDuplicates1;
console.log(listToString(test(arrayToList([1,2,3,3,4,4,5])))); // 1 -> 2 -> 5
console.log(listToString(test(arrayToList([1,1,1,2,3])))); // 2 -> 3
console.log(new Date().getTime() - start.getTime()); // 9
时间复杂度： 一次遍历，时间复杂度为$O(N)$
空间复杂度： 原地处理，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 28,2019